package cn.xkai.exercise.a;

import java.util.HashSet;
import java.util.Set;

/**
 * @description: 存在重复元素
 * 自己的思路：暴力遍历、排序+二分查找、set集合判断(时间复杂度O(n)、空间复杂度O(n))
 * 借鉴的思路：手写hash算法(时间复杂度O(n)、空间复杂度O(n))
 * 心得：set.contains底层循环实际O(n²)，hash只计算一次循环O(n)
 * @author: kaixiang
 * @date: 2022-07-01
 **/
public class Solution25 {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return true;
            }
            set.add(num);
        }
        return false;
    }

    public boolean containsDuplicateHash(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return false;
        }
        int[] hash = new int[len];
        int zoreCount = 0;
        for (int num : nums) {
            if (num == 0) {
                zoreCount++;
                if (zoreCount > 1) {
                    return true;
                }
                continue;
            }
            int k = num % len;
            if (k < 0) {
                k += len;
            }
            while (true) {
                if (hash[k] == 0) {
                    hash[k] = num;
                    break;
                } else if (hash[k] == num) {
                    return true;
                } else {
                    // hash冲突简单处理
                    k++;
                    if (k >= len) {
                        k -= len;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        Solution25 solution25 = new Solution25();
        System.out.println(solution25.containsDuplicateHash(nums));
    }
}
